/*
希尔排序是一种插入排序的改进版，通过将数组划分为多个子序列并分别进行插入排序，然后逐渐减少子序列的大小直到整个数组完全排序。它可以认为是插入排序的增强版本，通过“间距”缩短来提高排序效率。

在这个代码示例中，希尔排序函数 shell_sort 使用不同的“间距”来排序数组。在最初的循环中，间距从数组大小的一半开始，
然后每次迭代都减半。对于每个间距，内部循环进行一次插入排序，只是现在插入的位置不再是相邻的，而是相隔一个间距。
*/

#include <stdio.h>

// 希尔排序函数
void shell_sort(int arr[], int size) {
    // 初始间距，通常取数组大小的一半
    for (int gap = size / 2; gap > 0; gap /= 2) {
        // 对每个间距进行插入排序
        for (int i = gap; i < size; i++) {
            int temp = arr[i];  // 当前要插入的元素
            int j;

            // 按照间距对数组部分排序
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];  // 向右移动
            }

            // 将元素插入到正确位置
            arr[j] = temp;
        }
    }
}

int main() {
    // 示例数组
    int arr[] = {12, 34, 54, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    // 执行希尔排序
    shell_sort(arr, size);

    // 输出排序结果
    printf("排序后的数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}


